package jstudy.gu.kit.tree;

import java.io.Serializable;
import java.util.*;
import java.util.function.*;

import lombok.AllArgsConstructor;

// 通用的树形结构搜索., 单一类型 // dep - user
@AllArgsConstructor
public class TreeSearch<T> {
	private Function<Serializable, T> selectById; // 从数据库select 一条数据 selectById
	private BiConsumer<T, List<T>> setChildren;
	private Function<T, List<T>> getChildren;
	private Function<T, Serializable> getId; // T -> id
	private Function<T, Serializable> getParentId;
	private Predicate<T> isRoot;// 是否是根节点

	public List<T> search(List<T> flatNodes) {// 你要处理的节点的平面形式,也就是搜索的基本条目
		if (flatNodes == null || flatNodes.isEmpty()) {
			return flatNodes;
		}
		final List<T> roots = new LinkedList<>(); // 记载所有的根节点

		final Map<Serializable, T> nodes = new HashMap<>(); // 记录所有的节点,包括跟,缓存避免重复
		flatNodes.forEach(t -> nodes.put(getId.apply(t), t));// 先把所有基本节点缓存起来
		boolean processed = false; //是否处理过
		List<T> plist = flatNodes; // 要循环的节点,这是一个tmp节点,当前正在处理的节点列表
		Set<Serializable> rids = new HashSet<>();
		Serializable tid;
		while (!processed || !plist.isEmpty()) {
			processed = true;
			flatNodes = plist;
			plist = new LinkedList<>();
			for (T t : flatNodes) {
				if (isRoot.test(t) && !rids.contains((tid = getId.apply(t)))) {
					roots.add(t);
					rids.add(tid);
				} else {
					Serializable parentId = getParentId.apply(t);
					T parent = nodes.computeIfAbsent(parentId, selectById);
					// nodes 判断parentid 是否存在,如果存在,则直接返回,如果不存在,执行selectByID,.并且把结果存到nodes中
					if (parent != null) {
						List<T> pChildren = getChildren.apply(parent);
						if (pChildren == null) {
							pChildren = new ArrayList<>();
							setChildren.accept(parent, pChildren);
						}
						pChildren.add(t);
						if(!plist.contains(parent)) {
							plist.add(parent);
						}
					}

				}
			}
		}
		return roots;

	}

}